package code.daily;

import utils.ListNode;
import utils.TreeNode;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/29
 * @description TOP100有些没做的
 */
public class TOP100 {
    // 283. 移动零
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int slow = 0;
        for (int fast = 0; fast < len; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        while (slow < len) {
            nums[slow] = 0;
            slow++;
        }
    }

    // 438. 找到字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        // 1 <= s.length, p.length <= 3 * 104
        int len_s = s.length(), len_p = p.length();
        List<Integer> list = new ArrayList<>();
        // 如果s长度小于p，没有答案
        if (len_s < len_p)
            return list;
        // 把p中出现的所有字母及其数量记录一下
        int[] map = new int[26];
        for (int i = 0; i < len_p; i++) {
            char c = p.charAt(i);
            map[c - 'a']++;
        }
        // O(n)遍历s
        int[] rollMap = new int[26];
        for (int i = 0; i < len_p - 1; i++) {
            char c = s.charAt(i);
            rollMap[c - 'a']++;
        }
        for (int i = len_p - 1; i < len_s; i++) {
            // start = i - len_p + 1; end = i
            char c = s.charAt(i);
            rollMap[c - 'a']++;
            // 如果符合条件
            if (isOK438(map, rollMap))
                list.add(i - len_p + 1);
            // 滚动一下
            char c_last = s.charAt(i - len_p + 1);
            rollMap[c_last - 'a']--;
        }
        return list;
    }

    private boolean isOK438(int[] map, int[] rollMap) {
        for (int i = 0; i < 26; i++) {
            if (map[i] != rollMap[i])
                return false;
        }
        return true;
    }

    // 560. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        // 1 <= nums.length <= 2 * 104
        // 前缀和+哈希：对于i，我们要找，[j,i]的子数组和满足条件的个数count_j=[1,i]_(preSum[i]-preSum[j-1]==k)
        int len = nums.length;
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int[] preSum = new int[len + 1];
        preSum[1] = nums[0];
        for (int i = 2; i <= len; i++)
            preSum[i] = nums[i - 1] + preSum[i - 1];

        for (int i = 0; i <= len; i++) {
            // ans加上所有在i之前，前缀和 preSum[j] = preSum[i] - k 的情况
            // 这些情况都满足: preSum[i] - (preSum[i] - k) = k
            ans += map.getOrDefault(preSum[i] - k, 0);
            map.put(preSum[i], map.getOrDefault(preSum[i], 0) + 1);
        }
        return ans;
    }

    // 239. 滑动窗口最大值
    public int[] maxSlidingWindow_heap(int[] nums, int k) {
        // 方法一：建堆 O(nlogk)
        int n = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2[0], o1[0]));
        int[] ans = new int[n - k + 1];
        // 先加进去前面的k-1个
        for (int i = 0; i < k - 1; i++) {
            queue.offer(new int[]{nums[i], i});
        }
        // 每加一个，得到一个ans
        for (int i = k - 1; i < n; i++) {
            queue.add(new int[]{nums[i], i});
            // 如果当前最大值的下标不在[i-k+1, i]中，poll出去
            while (!queue.isEmpty() && queue.peek()[1] < i - k + 1)
                queue.poll();
            ans[i - k + 1] = queue.peek()[0];
        }
        return ans;
    }

    public int[] maxSlidingWindow_deque(int[] nums, int k) {
        // 方法二：双端队列 O(n) deque从first到last，存储的下标对应的值是递减的
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            // 清除不在范围的数据
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
                deque.removeFirst();
            // 当前值比之前的值大，说明前面的不可能成为答案了，去掉
            while (!deque.isEmpty() && num >= nums[deque.peekLast()])
                deque.removeLast();
            // 在队尾加上当前值（的下标）
            deque.addLast(i);

            if (i >= k - 1)
                ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

    // 76. 最小覆盖子串
    public String minWindow(String s, String t) {
        // 1 <= m, n <= 105   s 和 t 由英文字母组成 保证只有一个答案
        int m = s.length(), n = t.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> rollMap = new HashMap<>();
        int left = 0;
        int hit = 0;
        int minLen = Integer.MAX_VALUE;
        String ans = "";
        for (int right = 0; right < m; right++) {
            char c = s.charAt(right);
            // t中不包括c，不用管
            if (!map.containsKey(c))
                continue;
            // 如果不冗余，hit++
            if (rollMap.getOrDefault(c, 0) < map.get(c))
                hit++;
            rollMap.put(c, rollMap.getOrDefault(c, 0) + 1);
            // 满足条件，left向右
            while (hit == n) {
                // 更新答案
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    ans = s.substring(left, right + 1);
                }
                // 去掉left元素
                char cLeft = s.charAt(left);
                // 如果t中不包括cLeft，不用管
                if (map.containsKey(cLeft)) {
                    if (Objects.equals(rollMap.get(cLeft), map.get(cLeft)))
                        hit--;
                    rollMap.put(cLeft, rollMap.get(cLeft) - 1);
                }
                left++;
            }
        }
        return ans;
    }

    public String minWindow_optimized(String s, String t) {
        // 用数组作为map优化
        int m = s.length(), n = t.length();
        int[] map = new int[128];
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            map[c]++;
        }
        int[] rollMap = new int[128];
        int left = 0;
        int hit = 0;
        int minLen = Integer.MAX_VALUE;
        String ans = "";
        for (int right = 0; right < m; right++) {
            char c = s.charAt(right);
            // t中不包括c，不用管
            if (map[c] == 0)
                continue;
            // 如果不冗余，hit++
            if (rollMap[c] < map[c])
                hit++;
            rollMap[c]++;
            // 满足条件，left向右
            while (hit == n) {
                // 更新答案
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    ans = s.substring(left, right + 1);
                }
                // 去掉left元素
                char cLeft = s.charAt(left);
                // 如果t中不包括cLeft，不用管
                if (map[cLeft] > 0) {
                    if (rollMap[cLeft] == map[cLeft])
                        hit--;
                    rollMap[cLeft]--;
                }
                left++;
            }
        }
        return ans;
    }

    // 206. 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode left = null, right = head;
        while (right != null) {
            ListNode rightNext = right.next;
            right.next = left;
            left = right;
            right = rightNext;
        }
        return left;
    }

    // 25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        // 往后找k个，不够k个就不翻转
        // 先找前一组的尾和下一组的头，然后翻转这一组
        ListNode preLast = null, nextFirst;
        ListNode node = head;
        int count = 0;
        ListNode nowFirst = head, nowLast;
        boolean isReversed = false; // 表示是否进行过翻转（翻转了head节点变化）
        while (node != null) {
            count++;
            if (count == k) {
                // now 到 head 一共是k个
                nextFirst = node.next;
                // 翻转处理
                ListNode nowLeft = nowFirst;
                ListNode nowRight = nowFirst.next;
                while (nowRight != nextFirst) {
                    ListNode nowRightNext = nowRight.next;
                    nowRight.next = nowLeft;
                    nowLeft = nowRight;
                    nowRight = nowRightNext;
                }
                nowLast = nowLeft;

                // 上一组的最后一个的next设为当前组的最后一个（翻转后的第一个）
                if (preLast != null)
                    preLast.next = nowLast;
                // 当前组的第一个（翻转后变为最后一个）的next设为下一组的第一个
                nowFirst.next = nextFirst;
                // head节点变化
                if (!isReversed)
                    head = nowLast;
                isReversed = true;

                // 处理下一次
                preLast = nowFirst; // 更新preLast
                nowFirst = nextFirst; // 更新nowFirst
                node = preLast; // 更新node
                count = 0;
            }

            node = node.next;
        }
        return head;
    }

    // 41. 缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        // 要求时间O(n) 空间O(1)
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] >= 1 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return len + 1;
    }

    public int firstMissingPositive_3for(int[] nums) {
        int len = nums.length;
        // 第一个for：负数变最大值
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0)
                nums[i] = len + 1;
        }
        // 第二个for：把符合范围的标负
        for (int i = 0; i < len; i++) {
            int num = Math.abs(nums[i]);
            if (num > 0 && num <= len) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 第三个for：找第一个没有负号的数字下标
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }

    // 23. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
        ListNode preHead = new ListNode(0);
        ListNode node = preHead;
        for (ListNode listNode : lists) {
            if (listNode != null) queue.offer(listNode);
        }
        while (!queue.isEmpty()) {
            ListNode tempNode = queue.poll();
            if (tempNode.next != null)
                queue.offer(tempNode.next);
            node.next = tempNode;
            node = node.next;
            node.next = null;
        }
        return preHead.next;
    }

    // 240. 搜索二维矩阵 II
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target)
                return true;
            if (matrix[x][y] < target)
                x++;
            else
                y--;
        }
        return false;
    }

    // 994. 腐烂的橘子
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> queue = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2)
                    queue.offer(new int[]{i, j});
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                int x = pos[0], y = pos[1];
                if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    queue.offer(new int[]{x - 1, y});
                }
                if (x + 1 < m && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    queue.offer(new int[]{x + 1, y});
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    queue.offer(new int[]{x, y - 1});
                }
                if (y + 1 < n && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    queue.offer(new int[]{x, y + 1});
                }
            }
            // 他蔓延了，答案加一
            if (!queue.isEmpty())
                ans++;
        }
        for (int[] int_list : grid) {
            for (int j = 0; j < n; j++) {
                if (int_list[j] == 1)
                    return -1;
            }
        }
        return ans;
    }

    // 394. 字符串解码
    public String decodeString(String s) {
        // s 由小写英文字母、数字和方括号 '[]' 组成 1 <= s.length <= 30
        // stack_num 栈存放当前需要重复的次数
        // stack_pre 栈存放之前的字符串
        // sb 存放当前字符串
        Deque<Integer> stack_num = new LinkedList<>();
        Deque<String> stack_pre = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            char c = chars[i];
            // 如果是数字，则拿到完整数字
            if (Character.isDigit(c)) {
                int num = 0;
                int pos = i;
                while (Character.isDigit(chars[pos])) {
                    num = 10 * num + (chars[pos] - '0');
                    pos++;
                }
                i = pos - 1;
                // 数字入栈
                stack_num.push(num);
            }
            // 如果是左括号，当前sb入栈，sb清空
            else if (c == '[') {
                stack_pre.push(sb.toString());
                sb = new StringBuilder();
            }
            // 如果是右括号，构造当前的sb = stack_pre弹出来一个 + stack_num弹出来一个 × sb
            else if (c == ']') {
                String pre = stack_pre.pop();
                int times = stack_num.pop();
                String nowSB = sb.toString();
                sb = new StringBuilder();
                sb.append(pre);
                sb.append(nowSB.repeat(times));
            }
            // 如果是英文字符，sb append
            else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    // 160. 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // headA headB 都不为空
        ListNode a = headA, b = headB;
        // 如果有相交，最终ab相等在相交处，如果不相交，ab相等在null
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }

    // 234. 回文链表
    public boolean isPalindrome(ListNode head) {
        // 链表中节点数目在范围[1, 105] 内
        // 时间O(n)空间O(1)：先找到链表中点，翻转后半部分，然后双指针比较
        // 1-2-2-1
        // 1-2-3-2-1
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode r = slow.next, l = null;
        while (r != null) {
            ListNode rNext = r.next;
            r.next = l;
            l = r;
            r = rNext;
        }

        ListNode leftPos = head, rightPos = l;
        while (rightPos != null) {
            if (leftPos.val != rightPos.val)
                return false;
            leftPos = leftPos.next;
            rightPos = rightPos.next;
        }

        return true;
    }

    // 215. 数组中的第K个最大元素
    private int quickSelect(List<Integer> nums, int k) {
        // 随机选择基准数
        Random rand = new Random();
        int pivot = nums.get(rand.nextInt(nums.size()));
        // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot)
                big.add(num);
            else if (num < pivot)
                small.add(num);
            else
                equal.add(num);
        }
        // 第 k 大元素在 big 中，递归划分
        if (k <= big.size())
            return quickSelect(big, k);
        // 第 k 大元素在 equal 中，直接返回 pivot
        if (k <= big.size() + equal.size())
            return pivot;
        // 第 k 大元素在 small 中，递归划分
        return quickSelect(small, k - nums.size() + small.size());
    }

    public int findKthLargest_quick(int[] nums, int k) {
        // 类似快速排序：时间复杂度为O(n + n/2 + n/4 + ... + 1) = O(2n-1) = O(n)
        List<Integer> numList = new ArrayList<>();
        for (int num : nums)
            numList.add(num);
        return quickSelect(numList, k);
    }

    public int findKthLargest_heap(int[] nums, int k) {
        // 使用一个含有 k 个元素的最小堆 O(nlogk) 维护当前最大的k个元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        int n = nums.length;
        for (int i = k; i < n; i++) {
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > minHeap.peek()) {
                // Java 没有 replace()，所以得先 poll() 出来，然后再放回去
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }

    // 152. 乘积最大子数组
    public int maxProduct(int[] nums) {
        // 1 <= nums.length <= 2 * 104
        int len = nums.length;
        // 2 3 -2 4
        int[] dpMax = new int[len];
        int[] dpMin = new int[len];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            dpMin[i] = Math.min(dpMin[i - 1] * num, Math.min(dpMax[i - 1] * num, num));
            dpMax[i] = Math.max(dpMax[i - 1] * num, Math.max(dpMin[i - 1] * num, num));
            max = Math.max(max, dpMax[i]);
        }

        return max;
    }

    // 32. 最长有效括号
    public int longestValidParentheses(String s) {
        // 自己的做法：模拟
        int len = s.length();
        // 没出现一个（，记录这个（之前的答案
        Deque<Integer> prevStack = new LinkedList<>();
        int nowAns = 0;
        int max = 0;
        // ()(())(()())
        // stack =
        // nowAns =
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                prevStack.push(nowAns);
                nowAns = 0;
            } else {
                // 如果出现了多余的)，是不合法的，直接看下一个即可
                if (prevStack.isEmpty()) {
                    nowAns = 0;
                    continue;
                }
                int pos = i;
                int add = 0;
                // 碰到 ) 就把所有的合法的 ) 都搞出来
                while (pos < len && s.charAt(pos) == ')' && !prevStack.isEmpty()) {
                    pos++;
                    add += 2 + prevStack.pop();
                }
                i = pos - 1;
                nowAns += add;
                max = Math.max(max, nowAns);
            }
        }
        return max;
    }

    public int longestValidParentheses_stack(String s) {
        // 栈+索引：（传入 ）弹出   栈中实中要有一个前一位置索引
        int maxLen = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1); // 初始值，代表最左边界
        // ()(())(()())
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(')
                stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty())
                    stack.push(i);
                else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }

        return maxLen;
    }

    public int longestValidParentheses_dp(String s) {
        // 动态规划，dp[i]表示以s.charAt(i)结尾的满足条件的最大子数组长度
        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        // 当前是) 前一个是( dp[i] = dp[i-2] + 2
        // 当前是) 前一个是) s[i-dp[i-1]-1] 是 ( dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i);
            char prev = s.charAt(i - 1);
            if (c == ')') {
                if (prev == '(') {
                    dp[i] = 2;
                    if (i - 2 >= 0)
                        dp[i] += dp[i - 2];
                } else {
                    if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = 2 + dp[i - 1];
                        if (i - dp[i - 1] - 2 >= 0)
                            dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 75. 颜色分类
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        int i = l;
        while (i <= r) {
            if (nums[i] == 0) {
                swap75(nums, i, l);
                i++;
                l++;
            } else if (nums[i] == 2) {
                swap75(nums, i, r);
                r--;
            } else {
                i++;
            }
        }
    }

    private void swap75(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    // 136. 只出现一次的数字
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }

    // 287. 寻找重复数
    public int findDuplicate(int[] nums) {
        // 不修改数组、O(n)时间、O(n)空间
        // 抽象为链表，num表示下一个节点的下标，判断环在哪里
        // [3, 1, 3, 4, 2]
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int pos = 0;
        while (true) {
            visited[pos] = true;
            if (visited[nums[pos]])
                return nums[pos];
            pos = nums[pos];
        }
    }

    public int findDuplicate_o1space(int[] nums) {
        // 不修改数组、O(n)时间、O(1)空间
        // 141. 环形链表，142. 环形链表 II
        // *快慢指针找到相遇的节点，然后快指针从相遇节点出发，慢指针重新从开头出发，再次相遇的地方就是环开始的地方*
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    // 相关：141. 环形链表
    public boolean hasCycle(ListNode head) {
        // 链表中节点的数目范围是 [0, 104]
        if (head == null || head.next == null)
            return false;
        ListNode slow = head, fast = head;
        do {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return true;
        } while (slow != null && fast != null && fast.next != null);
        return false;
    }

    // 相关：142. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode slow = head, fast = head;
        do {
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != null && fast != null && fast.next != null && slow != fast);
        // 如果没有环，则null
        if (fast == null || fast.next == null)
            return null;
        // 有环，slow回到head，和fast一起走到相同即是答案
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    // 295. 数据流的中位数
    class MedianFinder {

        // 不断平衡small和large两个堆的元素个数
        PriorityQueue<Integer> small, large;

        public MedianFinder() {
            small = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
            large = new PriorityQueue<>();
        }

        // 我们要么让large和small个数相等，要么让large多一个
        public void addNum(int num) {
            // large为空，说明是第一个元素
            if (large.isEmpty()) {
                large.add(num);
                return;
            }

            if (num > large.peek()) {
                large.add(num);
                if (large.size() - small.size() == 2)
                    small.offer(large.poll());
            } else {
                small.add(num);
                if (small.size() > large.size())
                    large.offer(small.poll());
            }
        }

        public double findMedian() {
            if (large.size() > small.size())
                return large.peek();
            else
                return (large.peek() + small.peek()) / 2.0;
        }
    }

    // 4. 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    // 4. 寻找两个正序数组的中位数 (hard) todo 暂时放弃了
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        return 0;
    }

    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int target = -nums[i];
            int left = i + 1, right = len - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return lists;
    }

    // 24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        // 链表中节点的数目在范围 [0, 100] 内
        if (head == null)
            return null;
        ListNode preLast = null;
        ListNode nowFirst = head;
        boolean isHeadChanged = false;
        while (nowFirst != null) {
            // 确定这一次有俩，是可以交换的
            if (nowFirst.next == null)
                return head;
            ListNode nowSecond = nowFirst.next;
            ListNode nextFirst = nowSecond.next;
            if (!isHeadChanged) {
                isHeadChanged = true;
                head = nowSecond;
            }
            // 交换
            if (preLast != null)
                preLast.next = nowSecond;
            nowSecond.next = nowFirst;
            nowFirst.next = nextFirst;
            // 下一轮
            preLast = nowFirst;
            nowFirst = nextFirst;
        }
        return head;
    }

    // 146. LRU 缓存
    class DListNode {
        int key;
        int val;
        DListNode pre;
        DListNode next;

        public DListNode() {
            key = 0;
            val = 0;
            pre = null;
            next = null;
        }
    }
    class LRUCache {
        // LRU 缓存用 Map 和双向链表实现
        Map<Integer, DListNode> map;
        DListNode head;
        DListNode tail;
        int cap;
        int num;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            cap = capacity; // cap >= 1
            head = new DListNode(); // head - node1 - node2 - tail
            tail = new DListNode();
            head.next = tail;
            tail.pre = head;
            num = 0;
        }

        public int get(int key) {
            // 不存在 返回-1
            if (!map.containsKey(key))
                return -1;
            // 存在 移到head处 返回val
            DListNode node = map.get(key);
            DListNode nodePre = node.pre, nodeNext = node.next;
            nodePre.next = nodeNext;
            nodeNext.pre = nodePre;
            DListNode headNext = head.next;
            head.next = node;
            headNext.pre = node;
            node.pre = head;
            node.next = headNext;
            return node.val;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                // 如果存在，更新数值，移到head
                DListNode node = map.get(key);
                node.val = value;
                DListNode nodePre = node.pre, nodeNext = node.next;
                nodePre.next = nodeNext;
                nodeNext.pre = nodePre;
                DListNode headNext = head.next;
                head.next = node;
                headNext.pre = node;
                node.pre = head;
                node.next = headNext;
            } else {
                // 如果不存在，加上map，放到head
                num++;
                DListNode node = new DListNode();
                node.key = key;
                node.val = value;
                DListNode headNext = head.next;
                head.next = node;
                headNext.pre = node;
                node.pre = head;
                node.next = headNext;
                map.put(key, node);
                if (num > cap) {
                    // 删掉tail前的元素
                    num--;
                    DListNode nowDelete = tail.pre;
                    DListNode nowLast = nowDelete.pre;
                    nowLast.next = tail;
                    tail.pre = nowLast;
                    map.remove(nowDelete.key);
                }
            }
        }
    }

    // 94. 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        // 采用Morris遍历，没有额外空间
        List<Integer> list = new ArrayList<>();
        TreeNode node = root, pre = null;
        while (node != null) {
            // 如果左子树搞完了，就遍历自身，去右子树
            if (node.left == null || pre == node.left) {
                list.add(node.val);
                node = node.right;
                continue;
            }
            // 找到前驱结点
            pre = node.left;
            while (pre.right != null && pre.right != node) {
                pre = pre.right;
            }
            // 如果前驱结点的右子树为node，说明遍历过了，遍历自身，转向右子树
            if (pre.right == node) {
                pre.right = null;
                list.add(node.val);
                node = node.right;
            } else {
                pre.right = node;
                node = node.left;
            }
        }
        return list;
    }

    // 169. 多数元素
    public int majorityElement(int[] nums) {
        // 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
        // 摩尔投票算法：找到数组中大于等于半数的元素
        // 1 <= n <= 5 * 104
        int n = nums.length;
        int count = 0;
        int now = 0;
        for (int num : nums) {
            if (count == 0) {
                now = num;
                count++;
            } else {
                if (num == now)
                    count++;
                else
                    count--;
            }
        }
        return now;
    }

    // 31. 下一个排列
    public void nextPermutation(int[] nums) {
        // 必须 原地 修改，只允许使用额外常数空间。
        // 数比右面任何一个数小就行，但要找右面最小的那个数交换
        // 1 2 3 4 5
        // 1 2 3 5 4
        // 1 2 4 3 5
        // 1 2 4 5 3
        // 1 2 5 3 4
        // 1 2 5 4 3
        // 1 3 2 4 5
        int len = nums.length;
        for (int i = len - 2; i >= 0; i--) {
            // 如果这个数小于它右面的数，发生交换，与右面比他大的最小值交换
            if (nums[i] < nums[i + 1]) {
                int pos = i + 1;
                int smallestBigger = nums[i + 1];
                for (int j = pos + 1; j < len; j++) {
                    if (nums[j] > nums[i] && nums[j] <= smallestBigger) {
                        pos = j;
                        smallestBigger = nums[j];
                    }
                }
                swap31(nums, i, pos);
                reverse31(nums, i + 1, len - 1);
                return;
            }
        }
        // 如果到头了，reverse
        reverse31(nums, 0, len - 1);
    }

    private void swap31(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    private void reverse31(int[] nums, int left, int right) {
        while (left < right) {
            swap31(nums, left, right);
            left++;
            right--;
        }
    }

    // 62. 不同路径
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    // 64. 最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++)
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }

    // 5. 最长回文子串
    public String longestPalindrome(String s) {
        // 斜着遍历 dp[i][j] 表示从i到j的子串是否为回文子串 1 <= s.length <= 1000
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int maxLen = 1;
        int maxBegin = 0;
        for (int i = 0; i <= len - 1; i++)
            dp[i][i] = true;
        for (int i = 0; i <= len - 2; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                maxLen = 2;
                maxBegin = i;
            }
        }
        for (int L = 3; L <= len; L++) {
            for (int begin = 0; begin <= len - L; begin++) {
                int end = begin + L - 1;
                if (dp[begin + 1][end - 1] && s.charAt(begin) == s.charAt(end)) {
                    dp[begin][end] = true;
                    maxLen = L;
                    maxBegin = begin;
                }
            }
        }
        return s.substring(maxBegin, maxBegin + maxLen);
    }

    // 1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length(), l2 = text2.length();
        // dp[i][j] 表示text1到i，text2到j的最长公共子序列长度
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[l1][l2];
    }

    // 72. 编辑距离
    public int minDistance(String word1, String word2) {
        int l1 = word1.length(), l2 = word2.length();
        // dp[i][j]表示word1的前i个和word2的前j个相互转换所需最小距离
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 0; i <= l1; i++)
            dp[i][0] = i;
        for (int j = 0; j <= l2; j++)
            dp[0][j] = j;

        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                // 替换 删除 插入
                int change;
                // 相等时，替换不需要额外距离
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    change = dp[i - 1][j - 1];
                else
                    change = dp[i - 1][j - 1] + 1;
                int delete = dp[i - 1][j] + 1;
                int insert = dp[i][j - 1] + 1;
                dp[i][j] = Math.min(change, Math.min(delete, insert));
            }
        }
        return dp[l1][l2];
    }

    // 138. 随机链表的复制
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        Map<Node, Node> map = new HashMap<>();
        map.put(null, null);
        Node travelHead = head;
        while (travelHead != null) {
            map.put(travelHead, new Node(travelHead.val));
            travelHead = travelHead.next;
        }
        Node newHead = map.get(head);
        travelHead = head;
        while (travelHead != null) {
            newHead.next = map.get(travelHead.next);
            newHead.random = map.get(travelHead.random);
            travelHead = travelHead.next;
            newHead = newHead.next;
        }
        return map.get(head);
    }

    // 148. 排序链表
    public ListNode sortList(ListNode head) {
        // 链表天生适合用归并排序 链表中节点的数目在范围 [0, 5 * 10^4] 内
        // 用快慢指针拿到左右两个子链 递归执行 归并他们返回
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        // 归并
        ListNode preHead = new ListNode();
        ListNode node = preHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }
        if (left != null)
            node.next = left;
        else if (right != null)
            node.next = right;
        return preHead.next;
    }

    // 437. 路径总和 III
    int ans437 = 0;
    public int pathSum(TreeNode root, int targetSum) {
        // 前缀和为 key 的节点有 value 个
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        DFS437(root, map, targetSum, 0L);
        return ans437;
    }

    private void DFS437(TreeNode root, Map<Long, Integer> map, int targetSum, long sum) {
        if (root == null)
            return;
        // sum - xxx = targetSum
        sum += root.val;
        ans437 += map.getOrDefault(sum - targetSum, 0);
        // 加入
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        // dfs
        DFS437(root.left, map, targetSum, sum);
        DFS437(root.right, map, targetSum, sum);
        // 弹出
        if (map.get(sum) == 1)
            map.remove(sum);
        else
            map.put(sum, map.get(sum) - 1);
    }

    // 543. 二叉树的直径
    int ans543 = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        DFS543(root);
        return ans543;
    }

    private int DFS543(TreeNode root) {
        if (root == null)
            return 0;
        int left = DFS543(root.left);
        int right = DFS543(root.right);
        if (left + right > ans543)
            ans543 = left + right;
        return Math.max(left, right) + 1;
    }

    // 124. 二叉树中的最大路径和
    int ans124 = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        DFS124(root);
        return ans124;
    }

    private int DFS124(TreeNode root) {
        // 此函数返回带当前节点的单边最大路径和（不能同时选左和右）
        if (root == null)
            return 0;
        int leftMax = DFS124(root.left);
        int rightMax = DFS124(root.right);
        // 答案更新：1. 左+root+右 2. root 3. 右+root 4. 左+root
        ans124 = Math.max(ans124, Math.max(
                        Math.max(leftMax + root.val + rightMax, root.val),
                        Math.max(leftMax + root.val, rightMax + root.val)
                ));
        // 返回：1. root+单边 2. root
        return root.val + Math.max(Math.max(leftMax, rightMax), 0);
    }

    // 236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        TreeNode findLeft = lowestCommonAncestor(root.left, p, q);
        TreeNode findRight = lowestCommonAncestor(root.right, p, q);
        if (findLeft != null && findRight != null)
            return root;

        if (findLeft == null)
            return findRight;
        else
            return findLeft;
    }

    // 114. 二叉树展开为链表
    public void flatten(TreeNode root) {
        // 思路是：把左子树的 根节点到最右子树 插入到 node和node.right之间
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                TreeNode left = node.left, right = node.right;
                TreeNode leftMax = left;
                while (leftMax.right != null)
                    leftMax = leftMax.right;
                node.left = null; // 左子树置空
                node.right = left; // 左子树放到右子树的位置
                leftMax.right = right; // 左子树最右节点的右面接上原来的右面
            }
            node = node.right;
        }
    }

    // 207. 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 先记录所有的课程，作为一个拓扑图，记录每个课程（节点）的入度
        // 把所有入度为0的课程拿出来存在队列里
        // 当队列不为空时，遍历队列，并更新入度，如果入度为0再次放入队列中
        // 看最后能不能所有的节点入度都是0
        int[] in = new int[numCourses];
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new ArrayList<>();
        for (int[] prerequisite : prerequisites) {
            in[prerequisite[0]]++;
            graph[prerequisite[1]].add(prerequisite[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0)
                queue.offer(i);
        }
        int nowCourseNum = 0;
        while (!queue.isEmpty()) {
            int nowCourse = queue.poll();
            nowCourseNum++;
            for (int nextCourse : graph[nowCourse]) {
                in[nextCourse]--;
                if (in[nextCourse] == 0)
                    queue.offer(nextCourse);
            }
        }

        return nowCourseNum == numCourses;
    }

    // 208. 实现 Trie (前缀树)
    class TrieNode {
        // word 和 prefix 仅由小写英文字母组成
        boolean isWordEnd;
        TrieNode[] nextTrieNodes;
        public TrieNode() {
            nextTrieNodes = new TrieNode[26];
            isWordEnd = false;
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.nextTrieNodes[pos] == null)
                    node.nextTrieNodes[pos] = new TrieNode();
                node = node.nextTrieNodes[pos];
            }
            node.isWordEnd = true;
        }

        public boolean search(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.nextTrieNodes[pos] == null)
                    return false;
                node = node.nextTrieNodes[pos];
            }
            return node.isWordEnd;
        }

        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.nextTrieNodes[pos] == null)
                    return false;
                node = node.nextTrieNodes[pos];
            }
            return true;
        }
    }

    // 155. 最小栈
    class MinStack {
        // 用两个栈，min栈存储当前元素作为栈顶时，栈的最小元素
        Deque<Integer> stack;
        Deque<Integer> min;

        public MinStack() {
            stack = new LinkedList<>();
            min = new LinkedList<>();
        }

        public void push(int val) {
            stack.push(val);
            if (min.isEmpty())
                min.push(val);
            else
                min.push(Math.min(min.peek(), val));
        }

        public void pop() {
            stack.pop();
            min.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min.peek();
        }
    }
}

